package codingforgreat.class42;

import com.zrrd.tree.BinaryTree;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Problem_0272_ClosestBinarySearchTreeValueII {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public static List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> preStack = new Stack<>();
        Stack<TreeNode> posStack = new Stack<>();
        getPreStack(root,target,preStack);
        getPosStack(root,target,posStack);

        if(!preStack.isEmpty() && !posStack.isEmpty() && preStack.peek().val == posStack.peek().val ){
            getPredecessor(preStack);
        }
        while (k-->0){
            if(preStack.isEmpty()){
              ret.add(getPosdecessor(posStack));
            }else if (posStack.isEmpty()){
                ret.add(getPredecessor(preStack));
            }else{
                double diffs = Math.abs((double) posStack.peek().val - target);
                double diffp = Math.abs((double) preStack.peek().val - target);
                if (diffs < diffp) {
                    ret.add(getPosdecessor(posStack));
                } else {
                    ret.add(getPredecessor(preStack));
                }
            }

        }

        return ret;
    }
    public static void getPreStack(TreeNode root,double tar,Stack<TreeNode> stack){
        TreeNode node = root;
        while(node != null){
            if(tar < node.val){
                node = node.left;
            }else
            if(tar > node.val){
                stack.push(node);
                node = node.right;
            }else{
                stack.push(node);
                break;
            }
        }
    }
    public static void getPosStack(TreeNode root,double tar,Stack<TreeNode> stack){
        TreeNode node = root;
        while(node != null){
            if(tar < node.val){
                stack.push(node);
                node = node.left;
            }else
            if(tar > node.val){
                node = node.right;
            }else{
                stack.push(node);
                break;
            }
        }
    }
    public static int getPredecessor(Stack<TreeNode> preStack){
        TreeNode node = preStack.pop();
        int res = node.val;
        node = node.left;
        while(node != null){
            preStack.push(node);
            node = node.right;
        }
        return res;
    }
    public static int getPosdecessor(Stack<TreeNode> preStack){
        TreeNode node = preStack.pop();
        int res = node.val;
        node = node.right;
        while(node != null){
            preStack.push(node);
            node = node.left;
        }
        return res;
    }
}
